CF900D Unusual Sequences

建议先做 CF439E

n=1yi1=1yi2=1y...in=1y[ai=y][gcdai=x]\sum_{n=1}^y\sum_{i_1=1}^y\sum_{i_2=1}^y...\sum_{i_n=1}^y [\sum{a_i}=y][\gcd{a_i}=x]

n=1yi1=1yxi2=1yx...in=1yx[ai=yx][gcdai=1]\sum_{n=1}^y\sum_{i_1=1}^{\frac{y}{x}}\sum_{i_2=1}^\frac{y}{x}...\sum_{i_n=1}^\frac{y}{x} [\sum{a_i}=\frac{y}{x}][\gcd{a_i}=1]

n=1ydyxμ(d)i1=1yxdi2=1yxd...if=1yxd[ai=yxd]\sum_{n=1}^y\sum_{d|\frac{y}{x}} \mu(d) \sum_{i_1=1}^{\frac{y}{xd}}\sum_{i_2=1}^{\frac{y}{xd} }...\sum_{i_f=1}^{\frac{y}{xd}} [\sum{a_i}=\frac{y}{xd}]

后面枚举 ii 的过程可以看作将 yxd\frac{y}{xd} 个相同的球放进 nn 个不同的盒子,且不能有空盒的方案数,利用插板法可得: (yxd1n1)\binom{\frac{y}{xd}-1}{n-1}

那么原式即为:

n=1ydyxμ(d)(yxd1n1)\sum_{n=1}^y\sum_{d|\frac{y}{x}} \mu(d) \binom{\frac{y}{xd} - 1 }{n-1}

dyxμ(d)n=1y(yxd1n1)\sum_{d|\frac{y}{x}}\mu(d) \sum_{n=1}^y\binom{\frac{y}{xd} - 1 }{n-1}

dyxμ(d)n=1yxd(yxd1n1)\sum_{d|\frac{y}{x}}\mu(d) \sum_{n=1}^{\frac{y}{xd}}\binom{\frac{y}{xd} - 1 }{n-1}

dyxμ(d)n=1yxd(yxd1n1)\sum_{d|\frac{y}{x}}\mu(d) \sum_{n=1}^{\frac{y}{xd}}\binom{\frac{y}{xd} - 1 }{n-1}

dyxμ(d)2yxd1\sum_{d|\frac{y}{x}}\mu(d) 2^{\frac{y}{xd}-1}

#include <cstdio>

const int MAXN = 1e5 , Mod = 1e9 + 7;

int Quick_pow( int x , int po ) { int p = 1; for( ; po ; po >>= 1 , x = 1ll * x * x % Mod ) if( po & 1 ) p = 1ll * p * x % Mod; return p; }
int Inv( int x ) { return Quick_pow( x , Mod - 2 ); }

int mu( int n ) {
	int Ans = 1;
	for( int i = 2 ; i * i <= n ; i ++ )
		if( n % i == 0 ) {
			int p = 0; for( ; n % i == 0 ; n /= i ) p ++;
			if( p > 1 ) return 0;
			Ans *= -1;
		}
	if( n > 1 ) Ans *= -1;
	return Ans;
}

int x , y;
int main( ) {
	scanf("%d %d",&x,&y);
	if( y % x != 0 || y < x ) return printf("0\n") & 0;

	int Ans = 0;
	for( int d = 1 ; d * d <= y / x ; d ++ )
		if( y / x % d == 0 ) {
			Ans = ( Ans + mu( d ) * Quick_pow( 2 , y / x / d - 1 ) % Mod ) % Mod;
			if( d * d != y / x )
				Ans = ( Ans + mu( y / x / d ) * Quick_pow( 2 , d - 1 ) % Mod ) % Mod;
		}
	printf("%d\n", ( Ans + Mod ) % Mod );
	return 0;
}